﻿/*
 * BloomFilter original
 * Jim Mischel: Bloom Filters in C#
 * http://www.devsource.com/article2/0,1895,2113495,00.asp
 * Big thanks to the author
 * 
 * 1.1 2009-09-10 shootsoft Add() bug fixed, add Clear(), Save(), Load() methods
 *  
 */

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Xml;
using System.IO;
using ShootSearch.Util;

namespace ShootSearch.Common
{
    /// <summary>
    /// BloomFilter
    /// </summary>
    [Serializable]
    public class BloomFilter
    {
        /// <summary>
        /// Save and Load buffer size, default 5MB = 5* 1024 * 1024 byte
        /// </summary>
        public static int BufferSize = 5242880;
        /// <summary>
        /// Default key number
        /// </summary>
        public const int DEF_KEY_NUM = 12;

        private BitArray hashbits;
        private int numKeys;
        private int[] hashKeys;

        /// <summary>
        /// Gets the length of bloomfilter 
        /// </summary>
        public int TableSize { get { return hashbits.Length; } }

        /// <summary>
        /// Hash mark count, Default: 12
        /// </summary>        
        public int NumKeys
        {
            get { return numKeys; }
        }

        #region Constructor Method
        /// <summary>
        /// Constructor
        /// </summary>
        public BloomFilter()
        {

        }

        /// <summary>
        /// Constructor, with table size, default key number : 12
        /// </summary>
        /// <param name="tableSize">tableSize = Url size * 15</param>
        public BloomFilter(int tableSize)
        {
            Initialization(tableSize, DEF_KEY_NUM);
        }

        /// <summary>
        /// Constructor, with table size and key number
        /// </summary>
        /// <param name="tableSize">tableSize = Url size * 15</param>
        /// <param name="nKeys">minimum:3</param>
        public BloomFilter(int tableSize, int nKeys)
        {
            Initialization(tableSize, nKeys);
        }
        #endregion

        #region Private Method
        /// <summary>
        /// Set key number
        /// </summary>
        /// <param name="value"></param>
        private void SetNumKeys(int value)
        {
            if (value < 3)
            {
                numKeys = 3;
            }
            else numKeys = value;
            hashKeys = new int[numKeys];
        }



        /// <summary>
        /// Hash算法函数 CreateHashes,
        /// hi(x) = (f1(x) + if2(x)) mod m,
        /// 然后提供了一个 防止碰撞的结构. hashkeys 保存这个hash的三个位置
        /// </summary>
        /// <param name="str"></param>
        private void CreateHashes(string str)
        {
            int hash1 = str.GetHashCode();
            int hash2 = StringHasher.HashString(str);

            hashKeys[0] = Math.Abs(hash1 % hashbits.Count);
            if (numKeys > 1)
            {
                for (int i = 1; i < numKeys; i++)
                {
                    hashKeys[i] = Math.Abs((hash1 + (i * hash2))
                        % hashbits.Count);
                }
            }
        }
        #endregion

        #region Public Method
        /// <summary>
        /// Intialize the BloomFilter
        /// </summary>
        /// <param name="tableSize">tableSize = Url size * 15</param>
        /// <param name="nKeys">minimum:3</param>
        public void Initialization(int tableSize, int nKeys)
        {
            SetNumKeys(nKeys);
            hashbits = new BitArray(tableSize);
        }


        /// <summary>
        /// Check the existance of the string
        /// </summary>
        /// <param name="str">a string object</param>
        /// <returns>true exist,false does not exist</returns>
        public bool Contains(string str)
        {
            if (string.IsNullOrEmpty(str)) return false;
            CreateHashes(str);
            // Test each hash key.  Return false if any 
            //  one of the bits is not set.
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                    return false;
            }
            // All bits set.  The item is there.
            return true;
        }

        /// <summary>
        /// Add a string
        /// </summary>
        /// <param name="str">a string object</param>
        /// <returns>true add success, false add failed (exist already)</returns>
        public bool Add(string str)
        {
            if (string.IsNullOrEmpty(str)) return false;
            // Initially assume that the item is in the table
            bool rslt = false;
            CreateHashes(str);
            foreach (int hash in hashKeys)
            {
                if (!hashbits[hash])
                {
                    // One of the bits wasn't set, so show that
                    // the item wasn't in the table, and set that bit.
                    rslt = true;
                    hashbits[hash] = true;
                }
            }
            return rslt;
        }

        /// <summary>
        /// Clear the BloomFilter
        /// </summary>
        public void Clear()
        {
            hashbits = new BitArray(hashbits.Length);
        }

        /// <summary>
        /// Save a BloomFilter to the file
        /// </summary>
        /// <param name="fileName">the file path</param>
        public void Save(string fileName)
        {
            BinaryWriter bw = new BinaryWriter(
                new FileStream(fileName, FileMode.OpenOrCreate, FileAccess.Write,
                    FileShare.None, BufferSize));
            bw.Write(hashbits.Length);
            for (int i = 0; i < hashbits.Length; i++)
            {
                bw.Write(hashbits[i]);
            }
            bw.Close();

        }

        /// <summary>
        /// Load a BloomFilter from the file
        /// </summary>
        /// <param name="fileName">the file path</param>
        public void Load(string fileName)
        {
            FileStream fsRead = new FileStream(fileName, FileMode.Open, FileAccess.Read,
                  FileShare.None, BufferSize);
            BinaryReader br = new BinaryReader(fsRead);
            int length = br.ReadInt32();
            hashbits = new BitArray(length);
            for (int i = 0; i < length; i++)
            {
                hashbits[i] = br.ReadBoolean();
            }
            br.Close();
            fsRead.Close();

        }
        #endregion
    }

}
